package company;

import java.util.*;

/**
 * 127 单词接龙 bfs+dfs 也超出时间限制
 * 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
 * <p>
 * 每对相邻的单词之间仅有单个字母不同。
 * 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
 * 解释：存在 2 种最短的转换序列：
 * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
 * "hit" -> "hot" -> "lot" -> "log" -> "cog"
 * 示例 2：
 * <p>
 * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
 * 输出：[]
 * 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
 */
public class FindLaddersFour127 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String beginWords = sc.nextLine();
        String endWords = sc.nextLine();
        String[] split = sc.nextLine().split(",");
        List<String> wordIdList = new ArrayList<>(Arrays.asList(split));
        List<List<String>> ladders = findLadders(beginWords, endWords, wordIdList);
        for (List<String> list : ladders) {
            for (String word : list) {
                System.out.print(word + "->");
            }
            System.out.println();
        }
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if (!wordList.contains(endWord)) {
            return res;
        }
        // 找到所有邻居节点bfs+dfs
        Map<String, List<String>> map = new HashMap<>();
        bfs(beginWord, endWord, map, wordList);
        List<String> tmp = new ArrayList<>();
        tmp.add(beginWord);
        findLaddersHelper(beginWord, endWord, map, tmp, res);
        return res;
    }

    private static void findLaddersHelper(String beginWord, String endWord, Map<String, List<String>> map,
                                          List<String> temp, List<List<String>> ans) {
        if (beginWord.equals(endWord)) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        // 获取每个节点邻居节点
        List<String> list = map.getOrDefault(beginWord, new ArrayList<>());
        for (String neighbor : list) {
            temp.add(neighbor);
            findLaddersHelper(neighbor, endWord, map, temp, ans);
            temp.remove(temp.size() - 1);
        }
    }

    // 求所有邻居节点
    public static void bfs(String beginWord, String endWord, Map<String, List<String>> map, List<String> wordList) {
        Set<String> set1 = new HashSet<>();
        set1.add(beginWord);
        Set<String> set2 = new HashSet<>();
        set2.add(endWord);
        Set<String> dict = new HashSet<>(wordList);
        bfsHelper(set1, set2, dict, map, true);
    }

    public static boolean bfsHelper(Set<String> set1, Set<String> set2, Set<String> dict, Map<String, List<String>> map, boolean direction) {
        if (set1.isEmpty()) {
            return false;
        }
        if (set1.size() > set2.size()) {
            return bfsHelper(set2, set1, dict, map, !direction);
        }

        // 字典移除掉已经有的单词
        dict.removeAll(set1);
        dict.removeAll(set2);

        // 保存新扩展得到的节点
        Set<String> set = new HashSet<>();
        boolean done = false;

        for (String word : set1) {
            int len = word.length();
            char[] chars = word.toCharArray();
            for (char k = 'a'; k <= 'z'; k++) {
                for (int i = 0; i < len; i++) {
                    char tmp = chars[i];
                    if (tmp == k) {
                        continue;
                    }
                    chars[i] = k;
                    String newWord = String.valueOf(chars);
                    // 获取当前单词拓展的路径
                    // 根据方向得到 map 的 key 和 val
                    String key = direction ? word : newWord;
                    String val = direction ? newWord : word;
                    List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<>();
                    // 和set2相遇
                    if (set2.contains(newWord)) {
                        done = true;
                        list.add(val);
                        map.put(key, list);
                    }
                    //如果还没有相遇，并且新的单词在 word 中，那么就加到 set 中
                    if (!done && dict.contains(newWord)) {
                        set.add(newWord);
                        list.add(val);
                        map.put(key, list);
                    }
                    chars[i] = tmp;
                }
            }
        }
        //一般情况下新扩展的元素会多一些，所以我们下次反方向扩展  set2
        return done || bfsHelper(set2, set, dict, map, !direction);
    }
}
